package com.sheng.leetcode.year2023.month12.day05;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author by ls
 * @date 2023/12/5
 * <p>
 * 2477. 到达首都的最少油耗<p>
 * <p>
 * 给你一棵 n 个节点的树（一个无向、连通、无环图），每个节点表示一个城市，编号从 0 到 n - 1 ，且恰好有 n - 1 条路。<p>
 * 0 是首都。给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] ，表示城市 ai 和 bi 之间有一条 双向路 。<p>
 * 每个城市里有一个代表，他们都要去首都参加一个会议。<p>
 * 每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。<p>
 * 城市里的代表可以选择乘坐所在城市的车，或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。<p>
 * 请你返回到达首都最少需要多少升汽油。<p>
 * <p>
 * 示例 1：<p>
 * 输入：roads = [[0,1],[0,2],[0,3]], seats = 5<p>
 * 输出：3<p>
 * 解释：<p>
 * - 代表 1 直接到达首都，消耗 1 升汽油。<p>
 * - 代表 2 直接到达首都，消耗 1 升汽油。<p>
 * - 代表 3 直接到达首都，消耗 1 升汽油。<p>
 * 最少消耗 3 升汽油。<p>
 * <p>
 * 示例 2：<p>
 * 输入：roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2<p>
 * 输出：7<p>
 * 解释：<p>
 * - 代表 2 到达城市 3 ，消耗 1 升汽油。<p>
 * - 代表 2 和代表 3 一起到达城市 1 ，消耗 1 升汽油。<p>
 * - 代表 2 和代表 3 一起到达首都，消耗 1 升汽油。<p>
 * - 代表 1 直接到达首都，消耗 1 升汽油。<p>
 * - 代表 5 直接到达首都，消耗 1 升汽油。<p>
 * - 代表 6 到达城市 4 ，消耗 1 升汽油。<p>
 * - 代表 4 和代表 6 一起到达首都，消耗 1 升汽油。<p>
 * 最少消耗 7 升汽油。<p>
 * <p>
 * 示例 3：<p>
 * 输入：roads = [], seats = 1<p>
 * 输出：0<p>
 * 解释：没有代表需要从别的城市到达首都。<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 10^5<p>
 * roads.length == n - 1<p>
 * roads[i].length == 2<p>
 * 0 <= ai, bi < n<p>
 * ai != bi<p>
 * roads 表示一棵合法的树。<p>
 * 1 <= seats <= 10^5<p>
 */
public class LeetCode2477 {

    @Test
    public void test01() {
//        int[][] roads = {{0, 1}, {0, 2}, {0, 3}};
//        int seats = 5;
        int[][] roads = {{3, 1}, {3, 2}, {1, 0}, {0, 4}, {0, 5}, {4, 6}};
        int seats = 2;
//        int[][] roads = {};
//        int seats = 1;
        System.out.println(new Solution().minimumFuelCost(roads, seats));
    }
}

class Solution {

    List<Integer>[] lists;

    int seats;

    long ans;

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        ans = 0;
        this.seats = seats;
        lists = new List[n];
        Arrays.setAll(lists, o -> new ArrayList<>());
        // 记录连接
        for (int[] road : roads) {
            int x = road[0], y = road[1];
            lists[x].add(y);
            lists[y].add(x);
        }
        dfs(0, -1);
        return ans;
    }

    public int dfs(int x, int y) {
        int n = 1;
        for (Integer i : lists[x]) {
            if (i != y) {
                int dfs = dfs(i, x);
                ans += (dfs + seats - 1) / seats;
                n += dfs;
            }
        }
        return n;
    }
}
